// https://leetcode.cn/problems/reverse-nodes-in-k-group/

// 算法思路总结：
// 1. 计算需要反转的组数（链表长度/k）
// 2. 对每组进行头插法反转
// 3. 连接已反转组和剩余未反转部分
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include "LinkedListUtils.h"

class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        // 1.先求出要逆序的次数
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;

        // 2.开始逆序
        auto dummy = new ListNode(-1);
        auto prev = dummy;
        cur = head;
        for (int i = 0 ; i < n ; i++)
        {
            auto tmp = cur;
            for (int j = 0 ; j < k ; j++)
            {
                auto next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }

        // 3.处理不逆序的部分
        prev->next = cur;
        return dummy->next;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4,5}, v2 = {1,2,3,4,5};
    int k1 = 2, k2 = 3;
    auto l1 = createLinkedList(v1);
    auto l2 = createLinkedList(v2);

    Solution sol;
    auto r1 = sol.reverseKGroup(l1, k1);
    auto r2 = sol.reverseKGroup(l2, k2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}